package com.yangzhe.algorithm.c012;

// 给你一个链表的头节点 head 和一个特定值 x
// 请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
// 你应当 保留 两个分区中每个节点的初始相对位置
// 测试链接 : https://leetcode.cn/problems/partition-list/
public class PartitionList {
    /**
     * Definition for singly-linked list.
     */
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

	public static void main(String[] args) {
		ListNode node1 = new ListNode(1);
//		ListNode node2 = new ListNode(1);
//		ListNode node3 = new ListNode(3);
//		ListNode node4 = new ListNode(2);
//		ListNode node5 = new ListNode(5);
//		ListNode node6 = new ListNode(2);

		node1.next = null;
//		node2.next = null;
//		node3.next = node4;
//		node4.next = node5;
//		node5.next = node6;
//		node6.next = null;
		Solution solution = new Solution();
		printList(solution.partition(node1, 0));
	}

	public static void printList(ListNode head) {
		while (head != null) {
			System.out.print(head.val + ",");
			head = head.next;
		}
	}

    static class Solution {

		public ListNode partition(ListNode head, int x) {
			ListNode smallHead = null;
			ListNode smallTail = null;
			ListNode bigHead = null;
			ListNode bigTail = null;
			while (head != null) {
				ListNode next = head.next;
				head.next = null;
				if (head.val < x) {
					if (smallTail != null) {
						smallTail.next = head;
					}
					smallTail = head;
					if (smallHead == null) {
						smallHead = head;
					}
				} else {
					if (bigTail != null) {
						bigTail.next = head;
					}
					bigTail = head;

					if (bigHead == null) {
						bigHead = head;
					}

				}

				head = next;
			}

			if (smallTail != null) {
				smallTail.next = bigHead;
				return smallHead;
			} else {
				return bigHead;
			}
        }
    }
}
